#include<bits/stdc++.h>
using namespace std;
int m,n,add[300],del[300];
string str;
int main(){
	freopen("hw.in","r",stdin);
	freopen("hw.out","w",stdout);
	cin>>m>>n>>str;
	for(int i=1;i<=m;i++){
		char c;
		int ch;
		cin>>c;
		ch=int(c);
		cin>>add[ch]>>del[ch];
	} 
	if(n==2){
		if(str[0]==str[1]){
			cout<<0;
			return 0;
		}
		else{
			int a=del[str[0]],b=del[str[1]],c=add[str[0]],d=add[str[1]];
			cout<<min(a,min(b,min(c,d)));
			return 0;
		}
	}
	if(n==3){
		char a=str[0],b=str[1],c=str[2];
		if((a==b&&b==c)||(a==c)){
			cout<<0;
			return 0;
		}
		if(a==b||b==c){
			int f1=2*add[b],f2=del[a],f3=add[a],f4=del[b]*2;
			cout<<min(f1,min(f2,min(f3,f4)));
		}
//		else {
//			int f1=add[c]+add[b],f2=add[a]+add[c],f3=add[a]+add[b];
//			int f4=del[c]+add[a],f5=del[a]+add[c],f6=del[c]+add[a]
//		}
	}
	return 0;
}
